package 练习;

import java.util.ArrayList;
import java.util.List;

/**
 * Copyright (C) 2023 思创数码科技股份有限公司
 * <p/>
 * 版权所有
 * <p/>
 * 类名　　  : 找出所有相加之和为n的k个数的组合
 * 功能概要  :
 * 来源：LeetCode第216题
 * 难度：中等
 * <p>
 * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
 * <p>
 * 1，只使用数字1到9
 * <p>
 * 2，每个数字 最多使用一次
 *
 * @Author : yangwk
 * @Date : 2024/3/28 22:23
 */
public class 找出所有相加之和为n的k个数的组合 {
    public static void main(String[] args) {
        System.out.println(combinationSum3(3, 10));
    }

    public static List<List<Integer>> combinationSum3(int k, int n) {

        return combinationSum3(1, k, n, new ArrayList<>());
    }

    public static List<List<Integer>> combinationSum3(int start, int k, int n, List<Integer> path) {
        List<List<Integer>> result = new ArrayList<>();
        if (k < 0 || n < 0) {
            return result;
        }
        if (n == 0 && k == 0) {
            result.add(new ArrayList<>(path));
            return result;
        }
        for (int i = start; i <= 9; i++) {
            if (i > n) {
                break;
            }
            path.add(i);
            result.addAll(combinationSum3(i + 1, k - 1, n - i, path));
            path.remove(path.size() - 1);
        }
        return result;
    }


}
